package leecode.array.子串与子序列问题;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * @author wangxi created on 2021/5/12 23:50
 * @version v1.0
 *
 * https://leetcode-cn.com/problems/increasing-subsequences/
 *
 * 给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是 2 。
 *
 * https://leetcode-cn.com/problems/increasing-subsequences/solution/di-zeng-zi-xu-lie-by-leetcode-solution/
 */
public class IncreasingSubsequences {

    public static void main(String[] args) {
        IncreasingSubsequences obj = new IncreasingSubsequences();
        int[] nums = {1,2,8,6,4};
        List<List<Integer>> subsequences = obj.findSubsequences(nums);

        System.out.println(subsequences);

        int max = 0;
        for (List<Integer> list : subsequences) {
            max = Math.max(max, list.size());
        }
        List<List<Integer>> tempList = new ArrayList<>();
        for (List<Integer> list : subsequences) {
            if (list.size() == max) {
                tempList.add(list);
            }
        }
        tempList.sort(new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                StringBuilder buffer1 = new StringBuilder();
                StringBuilder buffer2 = new StringBuilder();
                for (int i = 0; i < o1.size(); i++) {
                    buffer1.append(o1.get(i));
                    buffer2.append(o2.get(i));
                }
                return buffer1.toString().compareTo(buffer2.toString());
            }
        });
        System.out.println(tempList.get(0));
    }

    List<Integer> temp = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        dfs(0, Integer.MIN_VALUE, nums);
        return ans;
    }

    public void dfs(int cur, int last, int[] nums) {
        if (cur == nums.length) {
            if (temp.size() >= 2) {
                ans.add(new ArrayList<Integer>(temp));
            }
            return;
        }
        if (nums[cur] >= last) {
            temp.add(nums[cur]);
            dfs(cur + 1, nums[cur], nums);
            temp.remove(temp.size() - 1);
        }
        if (nums[cur] != last) {
            dfs(cur + 1, last, nums);
        }
    }
}
